1316E - Team Building - CodeForces Solution

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define fast                      \
    ios_base::sync_with_stdio(0); \
    cin.tie(NULL);

// imp numbers
const ll INF = 1e18 + 7;
const ll MOD = 1e9 + 7;
const ll N = 1e6;

int main()
{
    fast;
    ll n, p, k;
    cin >> n >> p >> k;
    vector<pair<ll, ll>> vecp(n);
    for (ll i = 0; i < n; i++)
    {
        cin >> vecp[i].first;
        vecp[i].second = i;
    }
    ll score[n][p];
    for (ll i = 0; i < n; i++)
    {
        for (ll j = 0; j < p; j++)
        {
            cin >> score[i][j];
        }
    }
    sort(rall(vecp));
    ll dp[n + 1][(1LL << p) + 1];
    memset(dp, -1, sizeof(dp));
    dp[0][0] = 0;
    for (ll i = 1; i <= n; i++)
    {
        for (ll mask = 0; mask < (1LL << p); mask++)
        {
            ll selected = 0;

            // don't select this player in team
            ll remain = i - 1 - __builtin_popcount(mask);
            if (remain >= k)
            {
                if (dp[i - 1][mask] != -1)
                {
                    dp[i][mask] = dp[i - 1][mask];
                }
            }
            else
            {
                if (dp[i - 1][mask] != -1)
                {
                    dp[i][mask] = dp[i - 1][mask] + vecp[i - 1].first;
                }
            }
            // select at some position
            for (ll j = 0; j < p; j++)
            {
                if ((mask & (1 << j)) && dp[i - 1][(mask ^ (1LL << j))] != -1)
                {
                    dp[i][mask] = max(dp[i][mask], dp[i - 1][(mask ^ (1LL << j))] + score[vecp[i - 1].second][j]);
                }
            }
        }
    }
    cout << dp[n][(1LL << p) - 1] << "\n";
}
// NineFathoms